package com.leetcode.partition4;

import com.leetcode.common.TreeNode;

import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/8/23 10:57
 */
public class LC337打家劫舍3 {

    public static int rob(TreeNode root) {
//        return memoryRecursion(root, new HashMap<>());
        int[] res = dynamicProgrammingRecursion(root);
        return Math.max(res[0], res[1]);
    }

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(3, new TreeNode(2, null, new TreeNode(3)), new TreeNode(3, null, new TreeNode(1)));
        TreeNode root = new TreeNode(4, new TreeNode(1, new TreeNode(2, new TreeNode(3), null), null), null);
        System.out.println(rob(root));
    }

    /**
     * 动态规划型的递归，返回值为大小为2的数组，索引0表示当前节点不偷的最大收益，索引1位当前结点偷的最大收益
     */
    private static int[] dynamicProgrammingRecursion(TreeNode cur) {
        //空节点无论偷不偷都是0收益
        if (cur == null) return new int[]{0, 0};
        //需要对得到的结果进行比较，因此使用二叉树的后序遍历
        int[] leftValue = dynamicProgrammingRecursion(cur.left);
        int[] rightValue = dynamicProgrammingRecursion(cur.right);
        int curValue0 = Math.max(leftValue[0], leftValue[1]) + Math.max(rightValue[0], rightValue[1]);//如果当前结点不偷，可以偷子节点，也可以不偷子节点
        int curValue1 = cur.val + leftValue[0] + rightValue[0];     //如果当前节点偷了，就不能偷子节点
        System.out.println(curValue0 + "  " + curValue1);
        return new int[]{curValue0, curValue1};
    }

    //记忆化搜索
    private static int memoization(TreeNode cur, Map<TreeNode, Integer> cache) {
        if (cur == null) return 0;
        if (cur.left == null && cur.right == null) return cur.val;      //没有子节点，只能偷当前节点
        Integer resCache = cache.get(cur);          //如果缓存中已经有数据，则直接返回，没有数据则进行计算并存入缓存
        if (resCache != null) return resCache;
        int res1 = cur.val;         //偷父节点，子节点就不能偷，但是可以偷孙节点
        if (cur.left != null)
            res1 += memoization(cur.left.left, cache) + memoization(cur.left.right, cache);
        if (cur.right != null)
            res1 += memoization(cur.right.left, cache) + memoization(cur.right.right, cache);
        //不偷父节点，偷子节点
        int res2 = memoization(cur.left, cache) + memoization(cur.right, cache);
        //加入缓存
        cache.put(cur, Math.max(res1, res2));
        return Math.max(res1, res2);
    }
}
